package 排序算法;
/*
* 希尔排序推导
* */
public class xiErTest {
    static int[] arr1 = {3,5,1,-2,9,8,-5,10,-7};
    static int[] arr2 = new int[8000000];
    static{
        for (int i = 0; i < 8000000; i++) {
            arr2[i] = (int)(Math.random()*800000);
        }
    }
    public static void main(String[] args) {
        shellSort2(arr1);
        print(arr1);

        long begin = System.currentTimeMillis();
        long end = System.currentTimeMillis();
        System.out.println((end-begin));
    }


    /*
     * 希尔排序
     * 2.移动法
     * */
    public static void shellSort2(int[] arr){
        for (int gap = arr.length/2; gap > 0; gap /= 2) {// 分组次数
            for (int i = gap; i < arr.length; i++) {// 遍历每个分组
                int j = i;
                int insert = arr[j];
                    while (j - gap >= 0 && insert < arr[j - gap]) {
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    arr[j] = insert;
                }
        }
    }

    /*
     * 希尔排序
     * 1.交换法
     * */
    public static void shellSort1(int[] arr) {
        for (int gap = arr.length/2; gap > 0; gap /= 2) {// 分组次数
            for (int i = gap; i < arr.length; i++) {// 遍历每个分组
                for (int j = i-gap; j >= 0; j-=gap) {// 遍历分组元素
                    if(arr[j] > arr[j+gap]){// 交换
                        int temp = arr[j];
                        arr[j] = arr[j+gap];
                        arr[j+gap] = temp;
                    }
                }
            }
        }
    }

    public static void print(int [] arr){
        for (int j : arr) {
            System.out.print(j + " ");
        }
        System.out.println();
    }
}
